#include"BTree.h"

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

//申请空间
BTNode* BuyNode(BTDataType data)
{
  BTNode* Node=(BTNode*)malloc(sizeof(BTNode));
  Node->data=data;
  return Node;
}
//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n,int *pi)
{
  
  if(*pi>=n || a[*pi]=='#')
  {
    (*pi)++;
    return NULL;
  }

  BTNode* cur=(BTNode*)malloc(sizeof(BTNode));
  cur->data=a[*pi];
  (*pi)++;

  cur->left=BinaryTreeCreate(a,n,pi);
  cur->right=BinaryTreeCreate(a,n,pi);
  return cur;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
  assert(root);
  if(root)
  {
    BinaryTreeDestory(&(*root)->left);
    BinaryTreeDestory(&(*root)->right);
    free(*root);
    *root=NULL;
  }
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if(NULL==root) return 0; 
  return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if(NULL==root) return 0;
  if(root->left==NULL && root->right==NULL) return 1;
  return BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  if(NULL==root || k<1) return 0;
  if(1==k) return 1;
  return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}
// 二叉树的高度
int BinaryTreeHeight(BTNode*root)
{
  if(NULL==root) return 0;
  int left_height=BinaryTreeHeight(root->left);
  int right_height=BinaryTreeHeight(root->right);
  return 1+(left_height>right_height ? left_height : right_height);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if(NULL==root) return NULL;
  if(root->data==x) return root;
  BTNode* ret=BinaryTreeFind(root->left,x);
  if(ret)
  {
    return ret;
  }
  return BinaryTreeFind(root->right,x);
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if(root)
  {
    printf("%c ",root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
  }
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if(root)
  {
    BinaryTreeInOrder(root->left);
    printf("%c ",root->data);
    BinaryTreeInOrder(root->right);
  }
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if(root)
  {
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ",root->data);
  }
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

void TestBTNode()
{
  char str[]="ABD##E#H##CF##G##";
  int sz=sizeof(str)/sizeof(str[0]);
  int index=0;
  int k=3;
  BTNode* root = BinaryTreeCreate(str,sz,&index);
  printf("节点个数是:%d\n",BinaryTreeSize(root));
  BinaryTreePrevOrder(root);
  printf("\n");
  BinaryTreeInOrder(root);
  printf("\n");
  BinaryTreePostOrder(root);
  printf("\n");
  printf("叶子节点个数是:%d\n",BinaryTreeLeafSize(root));
  printf("第%d层节点的个数是:%d\n",k,BinaryTreeLevelKSize(root,k));
  printf("二叉树的高度为%d\n",BinaryTreeHeight(root));
  if(BinaryTreeFind(root,'E'))
  {
    printf("E在二叉树中\n");
  }
  else{
    printf("E不在二叉树中\n");
  }
  BinaryTreeDestory(&root);
}
